// 12. [2013 统考真题]已知一个整数序列A= (ao, a,.,an,-1)，,其中0≤a;<n (0≤i<n)。若
// 存在ap=ap2= .. =apm=x 且m>n/2 (0≤pr<n,1≤k≤m)，则称x为A的主元素。例
// 如A=(0,5,5,3,5, 7,5,5)，则5为主元素;又如A=(0,5,5,3,5, 1,5,7),则A中没有主
// 元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找
// 出A的主元素。若存在主元素，则输出该元素;否则输出-1。要求:
// 1 )给出算法的基本设计思想。
// 2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
// 3)说明你所设计算法的时间复杂度和空间复杂度。.

#pragma once
#include "vector"
#include "iostream"
template <typename ElemType>
void printVec(std::vector<ElemType> &vec)
{
    for (auto &i : vec)
    {
        std::cout << i << ",";
    }
    std::cout << "\r\n";
}
template <typename ElemType>
bool findVecMainElem(ElemType &retrun_find, std::vector<ElemType> &vec)
{
    ElemType elem = vec[0];
    int cnt = 1;
    for (int i = 1; i < vec.size(); i++)
    {
        if (elem == vec[i])
        {
            cnt++;
        }
        else
        {
            cnt--;
            if (cnt == 0)
            {
                elem = vec[i];
                cnt = 1;
            }
        }
    }
    cnt = 0;
    for (int i = 0; i < vec.size(); i++)
    {
        if (elem == vec[i])
        {
            cnt++;
        }
    }
    if (cnt > vec.size() / 2)
    {
        // return elem;
        retrun_find = elem;
        return true;
    }
    return false;
}
int main()
{
    std::cout << "hello \r\n";
    int arrA[] = {1, 2, 3, 3, 3, 3, 3, 3, 4, 10, 11};
    int arrB[] = {5, 6, 7, 8};
    // std::vector<int> A =
    //     std::vector<int> B =
    std::vector<int> A(arrA, arrA + sizeof(arrA) / sizeof(int));
    std::vector<int> B(arrB, arrB + sizeof(arrB) / sizeof(int));

    printVec(A);
    printVec(B);
    int find;
    if (findVecMainElem(find, A))
    {
        std::cout << "main is \r\n";
        std::cout << find //;
                  << "\r\n";
    }
    else
    {
        std::cout << "not find \r\n";
        // std::cout << findMiddleOfAB(B, A) //;
        //   << "\r\n";
    }

    // std::vector<int> vec1; // vec2, vec3;
    // int arr[100];
    // std::cout << "hello"
    //           << "\r\n";
    // //init data
    // for (int i = 0; i < 100; i++)
    // {
    //     arr[i] = i;
    // }
    // leftMoveArr(arr, 100, 30);

    // // fastFind(vec1, 9);
    // for (int i = 0; i < 100; i++)
    // {
    //     std::cout << arr[i] << ",";
    // }
    // std::cout << "\r\n";
    // for (int i = 0; i < vec2.size(); i++)
    // {
    //     std::cout << vec2[i] << ",";
    // }
    // std::cout << "\r\n";
    // ///////////////////////////////////////////////////
    // combineAB2C(vec1, vec2, vec3);
    // for (int i = 0; i < vec3.size(); i++)
    // {
    //     std::cout << vec3[i] << ",";
    // }
    // std::cout << "\r\n";
    return 0;
}